import java.util.Arrays;

public class TextDemo {
    public static void countSort(int[] array){
        if(array==null || array.length<=1){
            return ;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int value : array){
            if(value>max) max = value;
            if(value<min) min = value;
        }
        int range = max-min+1;
        int[] counting = new int[range];
        for(int value : array){
            counting[value-min]++;
        }
        counting[0]--;
        for(int i = 1;i<counting.length;i++){
            counting[i] += counting[i-1];
        }
        int[] result = new int[array.length];
        for(int i = array.length-1;i>=0;i--) {
            result[counting[array[i] - min]] = array[i];
            counting[array[i] - min]--;
        }
        for(int i = 0;i<array.length;i++){
            array[i] = result[i];
        }
    }
   public static void countingSort(int[] array){
       if(array==null || array.length<=1){
           return ;
       }
       int min = Integer.MAX_VALUE;
       int max = Integer.MIN_VALUE;
       for(int element : array){
           if(element>max) max = element;
           if (element<min) min = element;
       }
       int range = max-min+1;
       int[] counting = new int[range];
       for (int element : array){
           counting[element-min]++;
       }
       int prevCount = 0;
       for(int i = 0;i<counting.length;i++){
           prevCount+=counting[i];
           counting[i] = prevCount-counting[i];
       }
       int[] result = new int[array.length];
       for(int value : array){
           result[counting[value-min]] = value;
           counting[value-min]++;
       }
       for(int i = 0;i<array.length;i++){
           array[i] = result[i];
       }
   }
   public static void radixSort(int[] array){
        if(array == null){
            return ;
        }
        int max = Integer.MIN_VALUE;
        for(int value : array){
            if(value>max) max = value;
        }
        int maxDigitLength = 0;
        while(max!=0){
            maxDigitLength++;
            max/=10;
        }
        int dex = 1;
        int[] counting = new int[19];
        int[] result = new int[array.length];
        for(int i = 0;i<maxDigitLength;i++){
            for(int value : array){
                int radix = value/dex%10+9;
                counting[radix]++;
            }
            for(int j = 1;j<counting.length;j++){
                counting[j] += counting[j-1];
            }
            for(int j = array.length-1;j>=0;j--){
                int radix = array[j]/dex%10+9;
                result[--counting[radix]] = array[j];
            }
            System.arraycopy(result, 0, array, 0, array.length);
            // 将计数数组重置为 0
            Arrays.fill(counting, 0);


            dex*=10;
        }

   }
    public static void main(String[] args) {
        int[] array = new int[]{3,8,5,0,1,8,9,4,2,3,5,6,7,17,51,29,31,48,27,-10,-12,-9,-21};
        radixSort(array);
        System.out.println(Arrays.toString(array));
    }
   public static void radixSortNor(int[] array){
        if(array==null || array.length<=1){
            return ;
       }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int value : array){
            if(value > max) max = value;
            if(value < min) min = value;
        }
        int[] counting = new int[10];
        int maxDigitLength = 0;
        while(max!=0){
            maxDigitLength++;
            max/=10;
        }
        int[] result = new int[array.length];
        int div = 1;
        for(int i = 0;i<maxDigitLength;i++){
            //这里是给每个array里的元素的div位数的大小排序
            for(int value : array){
                int radix = value/div%10;
                counting[radix]++;
            }
            for(int j = 1;j<counting.length;j++){
                counting[j] = counting[j-1];
            }
            for(int j = array.length;i>=0;j--){
                int radix = array[j]/div%10;
                result[--counting[radix]] = array[j];
            }
            div*=10;
        }
   }




}
